#include <iostream>
#include <vector>

using namespace std;

// 106. 从中序与后序遍历序列构造二叉树
// 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x):val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {}
};
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        return buildTree(inorder,0,postorder,0,n);
    }
    void inorder(TreeNode* root) {
        if(root != nullptr) {
            inorder(root->left);
            cout << root->val << " ";
            inorder(root->right);
        }
    }
    void postorder(TreeNode* root) {
        if(root != nullptr) {
            postorder(root->left);
            postorder(root->right);
            cout << root->val << " ";
        }
    }
private:
    // 从 inorder 的 i 开始，postorder 的 j 开始，递归创建有n个结点的二叉树
    TreeNode* buildTree(vector<int>& inorder, int i, vector<int>& postorder, int j, int n) {
        if(n <= 0) return nullptr;
        int d = postorder[j+n-1];   // 获取根结点的值
        TreeNode* b = new TreeNode(d);
        int p = i;
        while(inorder[p] != d) p++;
        int k = p - i;  // 左子树的结点数
        b->left = buildTree(inorder,i,postorder,j,k);   // 递归创建左子树
        b->right = buildTree(inorder,p+1,postorder,j+k,n-k-1);  // 递归创建右子树
        return b;
    }

};
int main() {
    vector<int> inorder1({9,3,15,20,7});
    vector<int> postorder1({9,15,7,20,3});
    auto sln1 = Solution();
    TreeNode* tree1 = sln1.buildTree(inorder1,postorder1);
    sln1.inorder(tree1);
    cout << endl;
    sln1.postorder(tree1);

    return 0;
}
